/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2024-10-14
 * Time: 14:40
 */
public class test {
    /*
    LeetCode 746 最小花费爬楼梯
        给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

        你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

        请你计算并返回达到楼梯顶部的最低花费。
     */
    public int minCostClimbingStairs(int[] cost) {
        //从右往左执行

        int n = cost.length;
        int [] dp = new int [n];
        dp[n-1] = cost[n-1];
        dp[n-2] = cost[n-2];
        for(int i = n-3;i>=0;i--){
            dp[i] = Math.min(dp[i+1],dp[i+2])+cost[i];
        }
        return Math.min(dp[0],dp[1]);
    }

    public int minCostClimbingStairs2(int[] cost) {
        int n = cost.length;
        int [] dp = new int [n+1];
        dp[0] = dp[1] =0;
        for(int i =2;i<=n;i++){
            dp[i] = Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println("1");
    }


}



